﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/skFtm2/
/*
题目描述：
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

 

示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:
输入: nums =  [3,3,7,7,10,11,11]
输出: 10
 

提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
*/


// 开始解题：

// 方法1——针对奇偶序列的二分法

int singleNonDuplicate(int* nums, int numsSize) {
    assert(nums);
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    while (left < right) {
        mid = left + (right - left) / 2;
        mid -= mid & 1;
        if (nums[mid] == nums[mid + 1]) {
            left = mid + 2;
        }
        else {
            right = mid;
        }
    }
    return nums[left];
}